package arrray;

/**
 * @author huangxianjin
 * @date 2025/8/13 23:01
 * @description "买卖股票的最佳时机-升级版"
 */
public class LC_122 {
    //自己的做法-参考121
    public int maxProfit(int[] prices) {
        int sumProfit = 0;
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
        boolean flag = false;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
                sumProfit += maxProfit;
                flag = true;
            }
            if (flag) {
                minPrice = prices[i];
                maxProfit = 0;
                flag = false;
            }

        }
        return sumProfit;
    }

    //大佬的做法-直接遍历一遍，prices[i] > prices[i - 1]就加入到利润里，只累计增长部分
    public int maxProfit2(int[] prices) {
        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                int temp = prices[i] - prices[i - 1];
                sum += temp;
            }
        }
        return sum;
    }

    //官方做法-动态规划
    public int maxProfit3(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
}
